# 目标和(好题)
# leetcode第494题: https://leetcode.cn/problems/target-sum/description/
# 背包问题: https://www.bilibili.com/video/BV1o8411j73x
# Date: 2025/3/26
from leetcode import test_function as tf


def findTargetSumWays(nums: list[int], target: int) -> int:
    """设nums=[5,2,1,3] target = 1
    设应为正数的集合为pos, 负数的集合为neg, 那么本题中pos=[5, 1], neg=[2, 3]
    显然:
    sum(nums) = sum(pos) + sum(neg)
    target = sum(pos) - sum(neg)
    由上可得
    sum(pos) = (target + sum(nums)) / 2
    这就变成了一个背包问题的一个变种, 也就有多少种方式可以使得容量为sum(pos)的背包正好装满
    区别与此前的求背包的最大价值(重量), 本题的dp[j]不再是在重量为i时背包的最大价值(重量), 而是在重量为i时, 背包正好装满有多少种方式
    """
    pos = target + sum(nums)
    if pos % 2 != 0 or sum(nums) < abs(target):  # pos不是偶数, 无法组成target; 数组之和小于目标则无法组成target
        return 0
    pos //= 2

    dp = [0] * (pos + 1)
    dp[0] = 1
    for num in nums:
        for j in range(pos, num - 1, -1):
            dp[j] += dp[j - num]  # 这里的思路和<爬楼梯>这一道题很像

    return dp[pos]


if __name__ == '__main__':
    inp = [{"nums": [1, 1, 1, 1, 1], "target": 3}, {"nums": [1], "target": 1}, {"nums": [100], "target": -200}, ]
    out = [5, 1, 0]
    tf(findTargetSumWays, inp, out)
